/*
    * Copyright (C) 2009 The Guava Authors
    *
    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
    * in compliance with the License. You may obtain a copy of the License at
    *
    * http://www.apache.org/licenses/LICENSE-2.0
    *
    * Unless required by applicable law or agreed to in writing, software distributed under the License
   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
   * or implied. See the License for the specific language governing permissions and limitations under
   * the License.
   */
  
  package com.google.common.collect;
  
  import static com.google.common.base.Preconditions.checkNotNull;
  
  import com.google.common.annotations.GwtCompatible;
  
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.List;
  
  import javax.annotation.Nullable;
  
  /**
   * An implementation of {@link ImmutableTable} holding an arbitrary number of
   * cells.
   *
   * @author Gregory Kick
   */
  @GwtCompatible
  abstract class RegularImmutableTable<R, C, V> extends ImmutableTable<R, C, V> {
    RegularImmutableTable() {}
    
    abstract Cell<R, C, V> getCell(int iterationIndex);
    
    @Override
    final ImmutableSet<Cell<R, C, V>> createCellSet() {
      return isEmpty() ? ImmutableSet.<Cell<R, C, V>>of() : new CellSet();
    }
  
    private final class CellSet extends ImmutableSet<Cell<R, C, V>> {
      @Override
      public int size() {
        return RegularImmutableTable.this.size();
      }
  
      @Override
      public UnmodifiableIterator<Cell<R, C, V>> iterator() {
        return asList().iterator();
      }
  
      @Override
      ImmutableList<Cell<R, C, V>> createAsList() {
        return new ImmutableAsList<Cell<R, C, V>>() {
          @Override
          public Cell<R, C, V> get(int index) {
            return getCell(index);
          }
  
          @Override
          ImmutableCollection<Cell<R, C, V>> delegateCollection() {
            return CellSet.this;
          }
        };
      }
  
      @Override
      public boolean contains(@Nullable Object object) {
        if (object instanceof Cell) {
          Cell<?, ?, ?> cell = (Cell<?, ?, ?>) object;
          Object value = get(cell.getRowKey(), cell.getColumnKey());
          return value != null && value.equals(cell.getValue());
        }
        return false;
      }
  
      @Override
      boolean isPartialView() {
        return false;
      }
    }
    
    abstract V getValue(int iterationIndex);
  
    @Override
    final ImmutableCollection<V> createValues() {
      return isEmpty() ? ImmutableList.<V>of() : new Values();
    }
    
    private final class Values extends ImmutableList<V> {
      @Override
      public int size() {
        return RegularImmutableTable.this.size();
      }
  
      @Override
     public V get(int index) {
       return getValue(index);
     }
 
     @Override
     boolean isPartialView() {
       return true;
     }
   }
 
   static <R, C, V> RegularImmutableTable<R, C, V> forCells(
       List<Cell<R, C, V>> cells,
       @Nullable final Comparator<? super R> rowComparator,
       @Nullable final Comparator<? super C> columnComparator) {
     checkNotNull(cells);
     if (rowComparator != null || columnComparator != null) {
       /*
        * This sorting logic leads to a cellSet() ordering that may not be expected and that isn't
        * documented in the Javadoc. If a row Comparator is provided, cellSet() iterates across the
        * columns in the first row, the columns in the second row, etc. If a column Comparator is
        * provided but a row Comparator isn't, cellSet() iterates across the rows in the first
        * column, the rows in the second column, etc.
        */
       Comparator<Cell<R, C, V>> comparator = new Comparator<Cell<R, C, V>>() {
         @Override public int compare(Cell<R, C, V> cell1, Cell<R, C, V> cell2) {
           int rowCompare = (rowComparator == null) ? 0
             : rowComparator.compare(cell1.getRowKey(), cell2.getRowKey());
           if (rowCompare != 0) {
             return rowCompare;
           }
           return (columnComparator == null) ? 0
               : columnComparator.compare(cell1.getColumnKey(), cell2.getColumnKey());
         }
       };
       Collections.sort(cells, comparator);
     }
     return forCellsInternal(cells, rowComparator, columnComparator);
   }
 
   static <R, C, V> RegularImmutableTable<R, C, V> forCells(
       Iterable<Cell<R, C, V>> cells) {
     return forCellsInternal(cells, null, null);
   }
 
   /**
    * A factory that chooses the most space-efficient representation of the
    * table.
    */
   private static final <R, C, V> RegularImmutableTable<R, C, V>
       forCellsInternal(Iterable<Cell<R, C, V>> cells,
           @Nullable Comparator<? super R> rowComparator,
           @Nullable Comparator<? super C> columnComparator) {
     ImmutableSet.Builder<R> rowSpaceBuilder = ImmutableSet.builder();
     ImmutableSet.Builder<C> columnSpaceBuilder = ImmutableSet.builder();
     ImmutableList<Cell<R, C, V>> cellList = ImmutableList.copyOf(cells);
     for (Cell<R, C, V> cell : cellList) {
       rowSpaceBuilder.add(cell.getRowKey());
       columnSpaceBuilder.add(cell.getColumnKey());
     }
 
     ImmutableSet<R> rowSpace = rowSpaceBuilder.build();
     if (rowComparator != null) {
       List<R> rowList = Lists.newArrayList(rowSpace);
       Collections.sort(rowList, rowComparator);
       rowSpace = ImmutableSet.copyOf(rowList);
     }
     ImmutableSet<C> columnSpace = columnSpaceBuilder.build();
     if (columnComparator != null) {
       List<C> columnList = Lists.newArrayList(columnSpace);
       Collections.sort(columnList, columnComparator);
       columnSpace = ImmutableSet.copyOf(columnList);
     }
 
     // use a dense table if more than half of the cells have values
     // TODO(gak): tune this condition based on empirical evidence
     return (cellList.size() > (((long) rowSpace.size() * columnSpace.size()) / 2)) ?
         new DenseImmutableTable<R, C, V>(cellList, rowSpace, columnSpace) :
         new SparseImmutableTable<R, C, V>(cellList, rowSpace, columnSpace);
   }
 }